package com.zhanghp.class037;

import com.zhanghp.common.TreeNode;

/**
 * 验证搜索二叉树<br/>
 * 测试链接 : https://leetcode.cn/problems/validate-binary-search-tree/
 *
 * @author zhanghp
 * @since 2024/4/19 17:09
 */
public class Code05_ValidateBinarySearchTree {
    static class Solution {

        public static long min, max;

        public static boolean isValidBST(TreeNode head) {
            if (head == null) {
                // min是右孩子用，所以max
                min = Long.MAX_VALUE;
                // max是左孩子用，所以min
                max = Long.MIN_VALUE;
                return true;
            }
            boolean l = isValidBST(head.left);
            long lMin = min;
            long lMax = max;
            boolean r = isValidBST(head.right);
            long rMin = min;
            long rMax = max;
            // 获取最小，最大值，要带上root节点，一起获取
            // 左右孩子比较
            // min是右孩子用
            min = Math.min(Math.min(lMin, rMin), head.val);
            // max是左孩子用
            max = Math.max(Math.max(lMax, rMax), head.val);
            // lMax < root.val < rMin
            // 左右孩子都是搜索树
            return l && r && lMax < head.val &&  head.val < rMin;

        }

    }
}
